Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Rotate Image

Problem Statement

Given an n x n 2D matrix, modify a square matrix by rotating it 90 degrees in a clockwise direction.

Note: This rotation should be done in-place, meaning the transformation must occur within the original matrix without using any additional space for another matrix.

Examples

  • Example 1:
    • Input: matrix =
[[1,2],
 [3,4]]
  • Expected Output:
[[3,1],
 [4,2]]
  • Justification: After rotating the 2x2 matrix 90 degrees to the right, the element at the top left (1) moves to the top right, the top right (2) moves to the bottom right, the bottom right (4) moves to the bottom left, and the bottom left (3) moves to the top left.

  • Example 2:

    • Input: matrix =
[[5,1,9],
 [2,4,8],
 [13,3,6]]
  • Expected Output:
[[13,2,5],
 [3,4,1],
 [6,8,9]]
  • Justification: Rotating the 3x3 matrix 90 degrees to the right repositions the first row to the last column, the second row to the middle column, and the third row to the first column.

  • Example 3:

    • Input: matrix =
[[10,11,12,13],
 [14,15,16,17],
 [18,19,20,21],
 [22,23,24,25]]
  • Expected Output:
[[22,18,14,10],
 [23,19,15,11],
 [24,20,16,12],
 [25,21,17,13]]
  • Justification: The matrix is rotated by 90 degrees in the clockwise direction.

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Solution

To solve this problem, we'll employ a two-step approach: first, transpose the matrix, and then reverse each row. Transposing the matrix swaps the row and column indices for each element, effectively rotating the matrix by 90 degrees but in the wrong direction. Reversing each row afterward aligns the matrix correctly for the desired 90-degree rotation to the right.

This method is effective because it directly manipulates the matrix in place, adhering to the in-place requirement, and it systematically rearranges the elements to achieve the rotation without needing additional storage.

Step-by-step Algorithm

  1. Transpose the Matrix:

    • Iterate over the matrix with two nested loops, where the outer loop variable i runs from 0 to n-1 (inclusive) and the inner loop variable j runs from i to n-1 (inclusive).
    • For each pair (i, j), swap the elements at positions [i][j] and [j][i]. This effectively changes rows into columns, transposing the matrix.
  2. Reverse Each Row:

    • After the matrix is transposed, iterate over each row of the matrix with a single loop where the loop variable i runs from 0 to n-1 (inclusive).
    • For each row i, reverse the elements in the row. To do this, use a second loop where you swap elements from the start and end of the row moving towards the center. The loop variable j runs from 0 to (n/2)-1 (inclusive), and for each iteration, swap the elements at positions [i][j] and [i][n-1-j].

Algorithm Walkthrough

Let's consider the input:

[[10, 11, 12, 13],
 [14, 15, 16, 17],
 [18, 19, 20, 21],
 [22, 23, 24, 25]]
  1. Transpose the Matrix:

    • Swap (11, 14), (12, 18), (13, 22) for the first row.
    • Swap (16, 19), (17, 23) for the second row.
    • Swap (21, 24) for the third row.
    • The matrix after transposition:
      [[10, 14, 18, 22],
       [11, 15, 19, 23],
       [12, 16, 20, 24],
       [13, 17, 21, 25]]
      
  2. Reverse Each Row:

    • Reverse the first row: [22, 18, 14, 10]
    • Reverse the second row: [23, 19, 15, 11]
    • Reverse the third row: [24, 20, 16, 12]
    • Reverse the fourth row: [25, 21, 17, 13]
    • The final rotated matrix:
      [[22, 18, 14, 10],
       [23, 19, 15, 11],
       [24, 20, 16, 12],
       [25, 21, 17, 13]]
      

Each step transforms the matrix closer to the final rotated form. By first transposing the matrix, we align the rows and columns to their new orientations, and by then reversing each row, we correct the order of elements to match the 90-degree rotation to the right.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • : The algorithm iterates over each element of the matrix twice. First, during the transposition step, each element is visited once. Second, when reversing the rows, each element is again accessed once. Since the matrix is of size n x n, the total time complexity is .

Space Complexity

  • : The rotation is performed in-place, which means no additional storage is required beyond temporary variables that are used for swapping elements. This results in a constant space complexity.
Rotate Image (medium)
Combination Sum (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity